package done.normal_1001_1100;

import com.study.common.TreeNode;
import org.junit.Test;

import static com.study.util.LogUtil.info;

/**
 * 1008. Construct Binary Search Tree from Preorder Traversal 先序遍历构造二叉树
 * <p>
 * 返回与给定先序遍历 preorder 相匹配的二叉搜索树（binary search tree）的根结点。
 * <p>
 * (回想一下，二叉搜索树是二叉树的一种，其每个节点都满足以下规则，对于 node.left 的任何后代，
 * <p>
 * 值总 < node.val，而 node.right 的任何后代，值总 > node.val。此外，先序遍历首先显示节点的值，然后遍历 node.left，接着遍历 node.right。）
 * <p>
 * 示例：
 * 8
 * /   \
 * 5    10
 * / \    \
 * 1   7   12
 * <p>
 * 输入：[8,5,1,7,10,12]
 * 输出：[8,5,10,1,7,null,12]
 * <p>
 * 提示：
 * 1 <= preorder.length <= 100
 * 先序 preorder 中的值是不同的。
 * <p>
 * 2019-05-11 06:44
 **/
@SuppressWarnings("all")
public class ConstructBinarySearchTreeFromPreorderTraversal {

    public TreeNode bstFromPreorder(int[] preorder) {
        // 190511 first
        TreeNode root = null;
        for (int i = 0; i < preorder.length; i++)
            root = add(root, preorder[i]);

        return root;
    }

    private TreeNode add(TreeNode root, int num) {
        if (root == null)
            return new TreeNode(num);

        if (root.val > num)
            root.left = add(root.left, num);
        else
            root.right = add(root.right, num);

        return root;
    }

    @Test
    public void test() {
        info("[8, [5, [1, [7], [10, null, [12]]\n" +
                "08:47:39.287 [main] INFO com.study.util.LogUtil - {}", bstFromPreorder(new int[]{8, 5, 1, 7, 10, 12}));
    }
}











































/*
public TreeNode bstFromPreorder(int[] preorder) {
    TreeNode root = null;
    for (int i = 0; i < preorder.length; i++)
        root = add(root, preorder[i]);

    return root;
}

public TreeNode add(TreeNode root, int num) {
    if (root == null)
        return new TreeNode(num);

    if (root.val > num) {
        root.left = add(root.left, num);
    } else {
        root.right = add(root.right, num);
    }
    return root;
}
*/
